<!DOCTYPE html>
<!--
Copyright (c) 2014 The Chromium Authors. All rights reserved.
Use of this source code is governed by a BSD-style license that can be
found in the LICENSE file.
-->
<link rel="import" href="/tracing/base/base.html">
<script>
'use strict';

tr.exportTo('tr.b', function() {
  function max(a, b) {
    if (a === undefined) return b;
    if (b === undefined) return a;
    return Math.max(a, b);
  }

  /**
   * This class implements an interval tree.
   *    See: http://wikipedia.org/wiki/Interval_tree
   *
   * Internally the tree is a Red-Black tree. The insertion/colour is done using
   * the Left-leaning Red-Black Trees algorithm as described in:
   *       http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf
   *
   * @param {function} beginPositionCb Callback to retrieve the begin position.
   * @param {function} endPositionCb Callback to retrieve the end position.
   *
   * @constructor
   */
  function IntervalTree(beginPositionCb, endPositionCb) {
    this.beginPositionCb_ = beginPositionCb;
    this.endPositionCb_ = endPositionCb;

    this.root_ = undefined;
    this.size_ = 0;
  }

  IntervalTree.prototype = {
    /**
     * Insert events into the interval tree.
     *
     * @param {Object} datum The object to insert.
     */
    insert(datum) {
      const startPosition = this.beginPositionCb_(datum);
      const endPosition = this.endPositionCb_(datum);

      const node = new IntervalTreeNode(datum,
          startPosition, endPosition);
      this.size_++;

      this.root_ = this.insertNode_(this.root_, node);
      this.root_.colour = Colour.BLACK;
      return datum;
    },

    insertNode_(root, node) {
      if (root === undefined) return node;

      if (root.leftNode && root.leftNode.isRed &&
          root.rightNode && root.rightNode.isRed) {
        this.flipNodeColour_(root);
      }

      if (node.key < root.key) {
        root.leftNode = this.insertNode_(root.leftNode, node);
      } else if (node.key === root.key) {
        root.merge(node);
      } else {
        root.rightNode = this.insertNode_(root.rightNode, node);
      }

      if (root.rightNode && root.rightNode.isRed &&
          (root.leftNode === undefined || !root.leftNode.isRed)) {
        root = this.rotateLeft_(root);
      }

      if (root.leftNode && root.leftNode.isRed &&
          root.leftNode.leftNode && root.leftNode.leftNode.isRed) {
        root = this.rotateRight_(root);
      }

      return root;
    },

    rotateRight_(node) {
      const sibling = node.leftNode;
      node.leftNode = sibling.rightNode;
      sibling.rightNode = node;
      sibling.colour = node.colour;
      node.colour = Colour.RED;
      return sibling;
    },

    rotateLeft_(node) {
      const sibling = node.rightNode;
      node.rightNode = sibling.leftNode;
      sibling.leftNode = node;
      sibling.colour = node.colour;
      node.colour = Colour.RED;
      return sibling;
    },

    flipNodeColour_(node) {
      node.colour = this.flipColour_(node.colour);
      node.leftNode.colour = this.flipColour_(node.leftNode.colour);
      node.rightNode.colour = this.flipColour_(node.rightNode.colour);
    },

    flipColour_(colour) {
      return colour === Colour.RED ? Colour.BLACK : Colour.RED;
    },

    /* The high values are used to find intersection. It should be called after
     * all of the nodes are inserted. Doing it each insert is _slow_. */
    updateHighValues() {
      this.updateHighValues_(this.root_);
    },

    /* There is probably a smarter way to do this by starting from the inserted
     * node, but need to handle the rotations correctly. Went the easy route
     * for now. */
    updateHighValues_(node) {
      if (node === undefined) return undefined;

      node.maxHighLeft = this.updateHighValues_(node.leftNode);
      node.maxHighRight = this.updateHighValues_(node.rightNode);

      return max(max(node.maxHighLeft, node.highValue), node.maxHighRight);
    },

    validateFindArguments_(queryLow, queryHigh) {
      if (queryLow === undefined || queryHigh === undefined) {
        throw new Error('queryLow and queryHigh must be defined');
      }
      if ((typeof queryLow !== 'number') || (typeof queryHigh !== 'number')) {
        throw new Error('queryLow and queryHigh must be numbers');
      }
    },

    /**
     * Retrieve all overlapping intervals.
     *
     * @param {number} queryLow The low value for the intersection interval.
     * @param {number} queryHigh The high value for the intersection interval.
     * @return {Array} All [begin, end] pairs inside intersecting intervals.
     */
    findIntersection(queryLow, queryHigh) {
      this.validateFindArguments_(queryLow, queryHigh);
      if (this.root_ === undefined) return [];

      const ret = [];
      this.root_.appendIntersectionsInto_(ret, queryLow, queryHigh);
      return ret;
    },

    /**
     * Returns the number of nodes in the tree.
     */
    get size() {
      return this.size_;
    },

    /**
     * Returns the root node in the tree.
     */
    get root() {
      return this.root_;
    },

    /**
     * Dumps out the [lowValue, highValue] pairs for each node in depth-first
     * order.
     */
    dump_() {
      if (this.root_ === undefined) return [];
      return this.root_.dump();
    }
  };

  const Colour = {
    RED: 'red',
    BLACK: 'black'
  };

  function IntervalTreeNode(datum, lowValue, highValue) {
    this.lowValue_ = lowValue;

    this.data_ = [{
      datum,
      high: highValue,
      low: lowValue
    }];

    this.colour_ = Colour.RED;

    this.parentNode_ = undefined;
    this.leftNode_ = undefined;
    this.rightNode_ = undefined;

    this.maxHighLeft_ = undefined;
    this.maxHighRight_ = undefined;
  }

  IntervalTreeNode.prototype = {
    appendIntersectionsInto_(ret, queryLow, queryHigh) {
      /* This node starts has a start point at or further right then queryHigh
       * so we know this node is out and all right children are out. Just need
       * to check left */
      if (this.lowValue_ >= queryHigh) {
        if (!this.leftNode_) return;
        return this.leftNode_.appendIntersectionsInto_(
            ret, queryLow, queryHigh);
      }

      /* If we have a maximum left high value that is bigger then queryLow we
       * need to check left for matches */
      if (this.maxHighLeft_ > queryLow) {
        this.leftNode_.appendIntersectionsInto_(ret, queryLow, queryHigh);
      }

      /* We know that this node starts before queryHigh, if any of it's data
       * ends after queryLow we need to add those nodes */
      if (this.highValue > queryLow) {
        for (let i = (this.data.length - 1); i >= 0; --i) {
          /* data nodes are sorted by high value, so as soon as we see one
           * before low value we're done. */
          if (this.data[i].high < queryLow) break;

          ret.push(this.data[i].datum);
        }
      }

      /* check for matches in the right tree */
      if (this.rightNode_) {
        this.rightNode_.appendIntersectionsInto_(ret, queryLow, queryHigh);
      }
    },

    get colour() {
      return this.colour_;
    },

    set colour(colour) {
      this.colour_ = colour;
    },

    get key() {
      return this.lowValue_;
    },

    get lowValue() {
      return this.lowValue_;
    },

    get highValue() {
      return this.data_[this.data_.length - 1].high;
    },

    set leftNode(left) {
      this.leftNode_ = left;
    },

    get leftNode() {
      return this.leftNode_;
    },

    get hasLeftNode() {
      return this.leftNode_ !== undefined;
    },

    set rightNode(right) {
      this.rightNode_ = right;
    },

    get rightNode() {
      return this.rightNode_;
    },

    get hasRightNode() {
      return this.rightNode_ !== undefined;
    },

    set parentNode(parent) {
      this.parentNode_ = parent;
    },

    get parentNode() {
      return this.parentNode_;
    },

    get isRootNode() {
      return this.parentNode_ === undefined;
    },

    set maxHighLeft(high) {
      this.maxHighLeft_ = high;
    },

    get maxHighLeft() {
      return this.maxHighLeft_;
    },

    set maxHighRight(high) {
      this.maxHighRight_ = high;
    },

    get maxHighRight() {
      return this.maxHighRight_;
    },

    get data() {
      return this.data_;
    },

    get isRed() {
      return this.colour_ === Colour.RED;
    },

    merge(node) {
      for (let i = 0; i < node.data.length; i++) {
        this.data_.push(node.data[i]);
      }
      this.data_.sort(function(a, b) {
        return a.high - b.high;
      });
    },

    dump() {
      const ret = {};
      if (this.leftNode_) {
        ret.left = this.leftNode_.dump();
      }

      ret.data = this.data_.map(function(d) { return [d.low, d.high]; });

      if (this.rightNode_) {
        ret.right = this.rightNode_.dump();
      }

      return ret;
    }
  };

  return {
    IntervalTree,
  };
});
</script>
